#include <bits/stdc++.h>
using namespace std;

/*
2438. 二的幂数组中查询范围内的乘积
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个正整数 n ，你需要找到一个下标从 0 开始的数组 powers ，它包含 最少 数目的 2 的幂，且它们的和为 n 。powers 数组是 非递减 顺序的。根据前面描述，构造 powers 数组的方法是唯一的。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti] ，其中 queries[i] 表示请你求出满足 lefti <= j <= righti 的所有 powers[j] 的乘积。

请你返回一个数组 answers ，长度与 queries 的长度相同，其中 answers[i]是第 i 个查询的答案。由于查询的结果可能非常大，请你将每个 answers[i] 都对 109 + 7 取余 。

 

示例 1：

输入：n = 15, queries = [[0,1],[2,2],[0,3]]
输出：[2,4,64]
解释：
对于 n = 15 ，得到 powers = [1,2,4,8] 。没法得到元素数目更少的数组。
第 1 个查询的答案：powers[0] * powers[1] = 1 * 2 = 2 。
第 2 个查询的答案：powers[2] = 4 。
第 3 个查询的答案：powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64 。
每个答案对 109 + 7 取余得到的结果都相同，所以返回 [2,4,64] 。
示例 2：

输入：n = 2, queries = [[0,0]]
输出：[2]
解释：
对于 n = 2, powers = [2] 。
唯一一个查询的答案是 powers[0] = 2 。答案对 109 + 7 取余后结果相同，所以返回 [2] 。
 

提示：

1 <= n <= 109
1 <= queries.length <= 105
0 <= starti <= endi < powers.length
*/

// 法一
class Solution {
public:
    using ll = long long;
    const int MOD = 1e9 + 7;
    std::vector<int> productQueries(int n, std::vector<std::vector<int>>& queries) {
        // 用于存储由最少2的幂组成且和为n的数组
        std::vector<int> powers;
        // 记录当前2的幂的指数
        int i = 0;
        // 循环直到n变为0，即处理完n的所有二进制位
        while (n) {
            // 检查n的二进制表示的最低位是否为1
            if (n & 1) {
                // 如果最低位为1，将对应的2的幂（2^i）加入powers数组
                powers.push_back(1 << i);
            }
            // 将n右移一位，去掉已经检查过的最低位
            n >>= 1;
            // 指数i递增，为下一个2的幂做准备
            i++;
        }
        
        std::vector<int> ans;
        // 遍历每个查询
        for (const auto& query : queries) {
            // 获取查询区间的左边界
            int left = query[0];
            // 获取查询区间的右边界
            int right = query[1];
            // 初始化乘积为1
            ll product = 1;
            // 计算查询区间内powers数组元素的乘积
            for (int i = left; i <= right; i++) {
                product = (product * powers[i]) % MOD;
            }
            // 将乘积结果转换为int类型并加入结果数组ans
            ans.push_back(static_cast<int>(product));
        }
        return ans;
    }
};

// 法二
class Solution {
public:
    vector<int> productQueries(int n, vector<vector<int>>& queries) {
        const int MOD = 1e9 + 7;
        // powers数组用于存储组成n的最少数量的2的幂
        vector<int> powers;
        // 循环直至n为0，即所有位都处理完毕
        while (n) {
            // lowbit计算n的二进制表示中最低位的1及其后面的0组成的值，这是一个2的幂
            int lowbit = n & -n;
            powers.push_back(lowbit);
            // 通过异或操作将已经处理的最低位1去掉
            n ^= lowbit;
        }

        int m = powers.size();
        // res二维数组用于预先计算并存储powers数组中不同区间的乘积结果
        vector<vector<int>> res(m, vector<int>(m));
        // 初始化对角线元素，即单个元素的乘积就是其自身
        for (int i = 0; i < m; i++) {
            res[i][i] = powers[i];
            // 计算从i到j的区间乘积
            for (int j = i + 1; j < m; j++) {
                // res[i][j] 是res[i][j - 1] 与 powers[j] 的乘积并取模
                res[i][j] = 1LL * res[i][j - 1] * powers[j] % MOD;
            }
        }

        // ans数组用于存储所有查询的结果
        vector<int> ans;
        // 预先分配空间，避免多次重新分配内存
        ans.reserve(queries.size()); 
        for (auto& q : queries) {
            // 根据查询的区间直接从res数组中获取对应的乘积结果
            ans.push_back(res[q[0]][q[1]]);
        }
        return ans;
    }
};

// 法三
class Solution {
public:
    const int mod = 1e9 + 7;
    using ll = long long;
    // 辅助函数 快速幂
    ll fast_power(ll base, ll exp, ll mod) {
        ll res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp & 1) {
                res = (res * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }
        return res;
    }

    // 费马小定理 + 逆元
    vector<int> productQueries(int n, vector<vector<int>>& queries) {
        vector<int> powers;     // 分解二进制
        int i = 0;
        while (n) {
            if (n & 1)  // 最低位是否为1
                powers.push_back(1 << i);   // 2 ^ i push进数组  （1<<i = 2 ^ i）
            n >>= 1;    // 位运算 右移
            i++;        // 指数增加
        }
        // 此时power里面的1对应的幂 升序
        
        // 前缀数组
        int m = powers.size();
        vector<ll> prefix(m + 1);
        prefix[0] = 1;
        for (int i = 0; i < m; i++)     // 前缀积 
            prefix[i + 1] = (prefix[i] * powers[i]) % mod;
        
        // 前缀的模逆元
        vector<ll> inv_prefix(m + 1);
        for (int i = 0; i <= m; i++) {
            inv_prefix[i] = fast_power(prefix[i], mod - 2, mod);
        }
        
        vector<int> ans;        // 每一步查询
        for (auto& q : queries) {
            int left = q[0], right = q[1];
            ll res = (prefix[right + 1] * inv_prefix[left]) % mod;  // 区间乘积
            ans.push_back(static_cast<int>(res));
        }
        return ans;
    }
};